#include<stdio.h>
#include<cstdlib>
typedef int DateType;
//顺序表 定义
typedef struct{
	int MaxSize;
	DateType *data;
	int length;
}SeqList;
//链表定义
typedef struct LNode{
	DateType data;
	struct LNode * next;
} LNode,*LinkList;
//顺序表初始化
void InitList(SeqList &L, int n); 
// 顺序表输入
void Input_List(SeqList &L);
//顺序表输出
void Output_List(SeqList &L);
//顺序表合并
void Add_List(SeqList La,SeqList Lb,SeqList &Lc);
//顺序表
void List();

//链表初始化
void InitLink(LinkList &L);
//链表输入
void Input_Link(LinkList &L);
//链表输出
void Output_Link(LinkList L);
//链表合并
void Add_Link(LinkList La,LinkList Lb,LinkList &LC);
//链表
void Link(); 
//顺序表初始化
void InitList(SeqList &L,int n){
	L.data=(DateType *)malloc(n* sizeof(DateType));//每一次分配内存
	L.length=n;
	L.MaxSize=n; 
} 
 //顺序表输入
void Input_SeqList(SeqList &L){
	for(int i=0;i<L.MaxSize;i++){
		scanf("%d",&L.data[i]);//循环输入data值 
	}
	L.length=L.MaxSize;	 
} 
//顺序表输出
void Output_SeqList(SeqList L){
	for(int i=0;i<L.MaxSize;i++){
		printf("%d->, %d\t",i,L.data[i]);
	}
	printf("\n");
} 
//顺序表合并
void Add_SeqList(SeqList La,SeqList Lb,SeqList &Lc){
	int i=0,j=0,k=0;
	while(i<=La.length-1&&j<=Lb.length-1){
		if(La.data[i]<Lb.data[j]){
			Lc.data[k]=La.data[i];
			i++;k++;
		}
		else{
			Lc.data[k]=Lc.data[j];
			j++;k++;
		}
	}
	//当I中有剩余元素时 
	 while(i<=La.length-1){
	 	Lc.data[k]=La.data[i];
	 	i++;k++; 
	 }
	 //当Lb中有剩余元素时
	 while(j<=Lb.length-1){
	 	Lc.data[k]=Lb.data[j];
		 j++;k++; 
	 }  
	 Lc.length=La.length+Lb.length;
	 printf("L表长度为 %d",Lc.length);
	 printf("\n");
} 
void List(){
	int n;
	printf("请输入第一个升序排列的顺序表La\n");
	SeqList La;
	printf("请输入数据：");
	scanf("%d",&n);
	InitList(La,n);
	Input_SeqList(La);
	Output_SeqList(La);
	
	printf("请输入第二个升序排列的顺序表Lb：");
	SeqList Lb;
	printf("请输入数据：");
	scanf("%d",&n);
	InitList(Lb,n);
	Input_SeqList(Lb);
	Output_SeqList(Lb);
	 
	printf("合并成功");
	SeqList Lc;
	n=La.length+Lb.length;
	InitList(Lc,n);
	Add_SeqList(La,Lb,Lc); 
	Output_SeqList(Lc);
	 
}
//链表初始化 
void InitLink(LinkList &L){
	L=NULL;
}
//链表输入 
void Input_Link(LinkList &L){
	int x,n,i=1;
	printf("请输入数据");
	scanf("%d",&n);
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	while(i<=n){
		scanf("%d",&x);
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		i++;
	} 
	r->next=NULL;
	
}
//链表输出
void Ouput_Link(LinkList L){
	int j=1;
	LNode *p;
	p=L->next;
	while(p!=NULL){
		printf("%d->, %d\t",j,p->data);
		p=p->next;
		j++;
	} 
	printf("\n");
} 
//链表合并
void Add_Link(LinkList La,LinkList Lb,LinkList &Lc){
	Lc = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=Lc;
	LNode * la=La->next;
	LNode * lb=Lb->next;
	while(la!=NULL&&lb!=NULL){
		if(la->data<lb->data){
			s = (LNode *)malloc(sizeof(LNode));
			s->data=la->data;
			r->next=s;
			la=la->next;
			r=s;
			
		}
		else{
			s = (LNode *)malloc(sizeof(LNode));
			s->data=lb->data;
			r->next=s;
			lb=lb->next;
			r=s;			
		}
		r->next=NULL;
		
	}
	while(la!=NULL){
		s = (LNode *)malloc(sizeof(LNode));
		s->data=la->data;
		r->next=s;
		la=la->next;
		r=s;
		r->next=NULL;
		 
	}
	while(lb!=NULL){
		s = (LNode *)malloc(sizeof(LNode));
		s->data=lb->data;
		r->next=s;
		lb=lb->next;
		r=s;
		r->next=NULL;		
	}
	
} 
void Link(){
	printf("请输入第一个升序排列的链表La\n");
	LinkList La;
	InitLink(La);
	Input_Link(La);
	Ouput_Link(La);
	
	printf("请输入第二个升序排列的链表Lb\n");
	LinkList Lb;
	InitLink(Lb);
	Input_Link(Lb);
	Ouput_Link(Lb);
	
	printf("合并后链表Lc\n");
	LinkList Lc;
	Add_Link(La,Lb,Lc);
	Ouput_Link(Lc);

}

int main(){
	int a;
	printf("1.使用链表合并\n");
	printf("2.使用顺序表合并\n");
	printf("3.退出程序"); 
	while(1){
		printf("请输入需要的操作序号:");
		scanf("%d",&a);
		if(a==3) break;
		switch(a){
			case 1: Link();	continue;
			case 2: List();	continue;
		} 
	}
	return 0;
	} 
	
